#include<random>
#include<iostream>
#include<vector>
#include<ctime>
#include<algorithm>
#include"BinarySearchTree.h"
#include <iterator>
#include<chrono>
using namespace std;


template<typename Comparable>
void BSTsorting(std::vector<Comparable>& vec, int _mode =0)
{
	if (_mode == 0)
	{
		unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
		std::shuffle(vec.begin(), vec.end(),std::default_random_engine(seed));
	}
	BinarySearchTree<Comparable> tree;
	for (int i = 0; i < vec.size(); i++) {
		tree.insert(vec[i]);
	}
	//tree.printTree();
	cout << endl;
	clock_t begin, end;
	begin = clock();
	int size = vec.size();
	for (int i = 0; i < size; i++) {
		vec[i] = tree.findMin();
		tree.remove(tree.findMin());
	}
	end = clock();
	//	for (int i = 0; i < size; i++) {
	//		cout << vec[i] << " ";
	//	}
	cout << "time is " << double(end - begin) / CLOCKS_PER_SEC << endl;
	tree.makeEmpty();
}

template<typename Comparable>
void ShowVector(vector<Comparable>&vec)
{
	if (vec.size == 0)cout << "this is an empty vector";
	else {
		for (int i = 0; i < vec.size; i++) {
			cout << vec[i] << " ";
		}
	}
}

void TestNum100()
{
	vector<int>vec;
	BinarySearchTree<int> tree;
	for (int i = 0; i < 100; i++) {
		vec.push_back(i) ;
	}
	BSTsorting(vec,1);
	BSTsorting(vec, 0);
}

void TestNum1000()
{
        vector<int>vec;
        BinarySearchTree<int>tree;
        for(int i = 0; i < 1000; i++) {
        vec.push_back(i);
        }

        BSTsorting(vec,1);
        BSTsorting(vec,0);
}
void TestNum10000()
{
	vector<int>vec;
	BinarySearchTree<int> tree;
	for (int i = 0; i <10000; i++) {
		vec.push_back(i);
	}
	
	BSTsorting(vec, 1);
	BSTsorting(vec, 0);
}

void TestNum100000()
{
	vector<int>vec;
	BinarySearchTree<int> tree;
	for (int i = 0; i <100000; i++) {
		vec.push_back(i);
	}
	
	BSTsorting(vec, 1);
	BSTsorting(vec, 0);
}
int main()
{
	TestNum100();
	TestNum1000();
	TestNum10000();
	TestNum100000();
	
}
